package com.dailywork.basepro.stroper;

import java.util.ArrayList;
import java.util.Stack;
import java.util.stream.Collectors;
import java.util.stream.Stream;

import com.common.model.TreeNode;
import com.util.TreeOperUtil;

import scala.Char;

/**
 * 后缀表达式转变为表达式树
 * 
 * @author think
 */
public class Solution1 {

    public static void main(String[] args) {
        // String expression = "ab+cde+**";
        String expression = "1+(2+3)*4-5";
        TreeNode<String> tree = creatTree2(expression);
        System.out
                .println(Stream.of(TreeOperUtil.postScan(tree)).map(String::valueOf).collect(Collectors.joining(",")));
    }

    private static TreeNode<String> creatTree(String expression) {
        Stack<TreeNode<String>> stack = new Stack<>();
        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);
            if (ch != '+' && ch != '-' && ch != '*' && ch != '/') {
                TreeNode<String> node = new TreeNode<>(String.valueOf(ch));
                stack.push(node);
            } else {
                TreeNode<String> node = new TreeNode<>(String.valueOf(ch));
                TreeNode<String> rightNode = stack.pop();
                TreeNode<String> leftNode = stack.pop();
                node.setLeftChild(leftNode);
                node.setRightChild(rightNode);
                stack.push(node);
            }

        }
        return stack.pop();
    }

    public static TreeNode<String> creatTree2(String str) {
        // 声明一个数组列表，存放的操作符，加减乘除
        ArrayList<String> operList = new ArrayList<String>();
        // 声明一个数组列表，存放节点的数据
        ArrayList<TreeNode<String>> numList = new ArrayList<>();
        String s = "";
        // 第一，辨析出操作符与数据，存放在相应的列表中
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (ch >= '0' && ch <= '9') {
                s += ch;
            } else {
                numList.add(new TreeNode<>(s));
                s = "";
                operList.add(ch + "");

            }

        }
        // 把最后的数字加入到数字节点中
        numList.add(new TreeNode<>(s));

        while (operList.size() > 0) {
            TreeNode<String> left = numList.remove(0);
            TreeNode<String> right = numList.remove(0);
            String oper = operList.remove(0);

            TreeNode<String> node = new TreeNode<>(oper);
            node.setLeftChild(left);
            node.setRightChild(right);
            numList.add(0, node);

        }
        // 第四步，让根节点等于最后一个节点
        return numList.get(0);
    }
}